﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0032_SearchInsert : IAlgorithm
    {
        // 35. 搜索插入位置

        // 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

        // 请必须使用时间复杂度为 O(log n) 的算法。

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { -1, 0, 3, 5, 9, 12 };
            int target = -2;
            // 算法执行与打印
            Console.WriteLine(SearchInsert(nums, target));
        }

        // 算法
        // 二分法
        public int SearchInsert(int[] nums, int target)
        {
            int s = 0, e = nums.Length - 1;
            while (s <= e)
            {
                // m有坑 不能两个除2
                var m = (e - s) / 2 + s;
                if (nums[m] == target)
                    return m;
                else if (nums[m] > target)
                    e = m - 1;
                else
                    s = m + 1;
            }
            // 比最后一个数小，则e--，比最后一个数大，则e不变，而此时e是最后一个数的下标
            return e + 1;
        }
    }
}
